// 2025/3/2
// https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-100-liked
// 接雨水

// 动态规划
class Solution {
    public:
        int trap(vector<int>& height) {
            int n = height.size();
            vector<int> leftMax(n, 0), rightMax(n, 0);
            leftMax[0] = height[0];
            rightMax[n - 1] = height[n - 1];
            for(int left = 1; left < n; left++)
            {
                leftMax[left] = max(height[left], leftMax[left - 1]);
                int right = n - 1 - left;
                rightMax[right] = max(height[right], rightMax[right + 1]);
            }
    
            int ans = 0;
            for(int i = 0; i < n; i++)
            {
                ans += min(leftMax[i], rightMax[i]) - height[i];
            }
            return ans;
        }
};

// 单调栈
class Solution {
    public:
        int trap(vector<int>& height) {
            int n = height.size(), ans = 0;
            stack<int> st;
            for(int right = 0; right < n; right++)
            {
                while(!st.empty() && height[right] > height[st.top()])
                {
                    int top = st.top();
                    st.pop();
                    if(st.empty()) break;
    
                    int left = st.top();
                    int curWidth = right - left - 1;
                    int curHeight = min(height[left], height[right]) - height[top];
                    ans += curWidth * curHeight;
                }
                st.push(right);
            }
            return ans;
        }
};

// 双指针
class Solution {
    public:
        int trap(vector<int>& height) {
            int n = height.size(), ans = 0;
            int left = 1, right = n - 2;
            int leftMax = height[0], rightMax = height[n - 1];
    
            while(left <= right)
            {
                leftMax = max(leftMax, height[left]);
                rightMax = max(rightMax, height[right]);
    
                if(leftMax > rightMax)
                {
                    ans += rightMax - height[right];
                    --right;
                }
                else
                {
                    ans += leftMax - height[left];
                    ++left;
                }
            }
            return ans;
        }
};